package MysingleListPractice_Once_time;

import com.sun.org.apache.xalan.internal.lib.NodeInfo;

public class MysingleList {
    static class Node{
        int val;
        Node next;
        public Node(int val){
            this.val=val;
        }
    }
    public Node head;
    public void createLink(){
        Node node=new Node(12);
        Node node1=new Node(45);
        Node node2=new Node(23);
        Node node3=new Node(90);
        Node node4=new Node(100);
        node.next=node1;//node代表一种引用，是地址类型
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        head=node;
    }
    //遍历链表
    public void display(){
        Node cur=head;
        while (cur!=null){
            System.out.println("当前cur的值为："+cur.val);
            cur=cur.next;
        }
    }
    //从指定位置开始展示

    public void display(Node head){
        Node cur=head;
        while (cur!=null){
            System.out.println("当前cur的值为："+cur.val);
            cur=cur.next;
        }
    }
    //判断某个值是否在链表中存在
    public boolean contains(int key){
        Node cur =head;
        while(cur!=null){
            if (cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //计算单链表长度
    public int size(){
        int count=0;
        Node cur=head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //头插法
    public void addFirst(int data){
        Node node=new Node(data);
        node.next=head;
        head=node;
    }
    //尾插法
    public void  addLast(int data){
        Node node=new Node(data);
        if (head==null){//无节点
            head=node;
            return;
        }
        Node cur=head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }
    //指定位置插入
    public void addIndex  (int index,int data) throws ListIndexOutOfException{
        checkIndex(index);
        if (index==0){
            addFirst(data);
            return;
        }
        if (index==size()){
            addLast(data);
            return;
        }
        Node node=new Node(data);
        Node cur=findIndexSubOne(index);
        node.next=cur.next;
        cur.next=node;
    }
    //检查下标合法
    private void checkIndex(int index){
        if (index<0||index>size()){
            throw new ListIndexOutOfException("index位置不合法");
        }
    }
    //先找到指定位置
    private Node findIndexSubOne(int index){
        Node cur=head;
        int count=0;
        while (count!=index-1){
            cur=cur.next;
            count++;
        }//执行完循环，cur走到index的前一个
        return cur;
    }
    //删除第一次出现的key关键字的节点
    public void remove(int key){
        if (head.val==key){
            head=head.next;
            return;
        }
        Node cur=searchPrev(key);
        if (cur==null){
            return;
        }
        Node del=cur.next;//已被删除，不接入链表
        cur.next=del.next;
    }
    //遍历到要删除节点的前一个节点
    private Node searchPrev(int key){
        if (head==null){
            return null;
        }
        Node cur=head;
        while (cur!=null){
            if (cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
    //删除所有为Key的节点
    public void removeAllkey(int key){
        if (head==null){
            return;
        }

        Node prev=head;
        Node cur=head.next;
        //找到要删除的值
        while (cur!=null){
            if (cur.val==key){//找到key
                prev.next=cur.next;//跳过key节点,此时prev没动
                cur=cur.next;
            }else {
                prev=cur;
                cur=cur.next;//该节点不是目标值，继续往后走
            }
        }
        //处理头节点的情况
        if (head.val==key){
            head=head.next;
        }
    }
    //递归删除所有为val的节点
    public Node removeElements(Node head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val);//如果值相等：head.next=head.next
        return head.val == val ? head.next : head;
        //   如果节点的值＝val，返回头节点的next节点，否则返回head节点
    }
    //清空链表
    public void clead(){
        head=null;
    }
    //反转链表
    public Node reverseList(){
        if (head==null||head.next==null){
            return head;
        }
        Node cur=head.next;
        head.next=null;
        while(cur!=null){
            Node curNext=cur.next;//记录cur的后一个节点
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
    //返回链表的中间节点
    public Node middleNode(){//快慢指针
        if (head==null){
            return null;
        }
        Node slow=head;
        Node fast=head;
        //如果是奇数的情况，使用"||"，右边的fast.next!=null会被短路
        //fast!=null是fast.next!=null的前提
        while (fast!=null&&fast.next!=null){//奇数走完是fast.next为空，偶数是fast为null
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
    //递归打印单向链表
    public void display3(Node head){
        if (head==null){
            return ;
        }
        if (head.next==null){
            System.out.println(head.val+" ");
            return;
        }
        display3(head.next);
        System.out.println(head.val+" ");
    }
    //返回倒数第k个节点
    //slow和fast相差k-1步
    //快慢指针
    public Node findkthTotial(int k){
        if (k<0||head==null){
            return null;
        }
        Node fast=head;
        Node slow=head;
        //先让fast走k-1步,假如返回倒数第3个节点，那么slow和fast必须相差3-1=2步
        //这样当fast.next=null的时候，slow就指向倒数第k个节点
        while (k-1!=0){
            fast=fast.next;
            k--;
        }
        while (fast!=null&&fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    //判断是否回文
    public boolean chkPalindrome(){
        if (head==null){
            return false;
        }
        if (head.next==null){//只有一个节点
            return true;
        }
        Node midNode=middleNode();//找到中间节点
        //此时中间节点的next的值不是Null，而是没有反转之前的下一个节点的值

        /*Node fast=head;
        Node slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }*/
        Node cur=midNode.next;//从mid的后一个节点开始反转
        while (cur!=null){
            Node nodeNext=cur.next;
            cur.next=midNode;
            midNode=cur;
            cur= nodeNext;
        }
        //运行到这里Mid在后半部分的头节点这里
        //前后对比是否相等，一个往后，一个往前
        while (midNode!=head){
            if (midNode.val!=head.val){
                return false;
            }
            //偶数情况
            //1   ——》  1   ——》    1   《——   1
            //                   中间节点
            if (head.next==midNode){
                return true;
            }
            //值相等就继续往后/往前走
            midNode=midNode.next;
            head=head.next;
        }
        //while运行完证明一直相等
        return true;

    }
    //以某个x值为基准，将大于该值的节点排在后面，小于该值的节点排在前
    //分为before和after两条链表
    public Node partition(int x){
        Node beforeEnd=null;//动他
        Node beforeStart=null;
        Node afterEnd=null;//动他
        Node afterStart=null;
        Node cur=head;
        while (cur!=null){
            if (cur.val<x){
                if (beforeStart==null){
                    beforeStart=cur;
                    beforeEnd=cur;
                }else {
                    beforeEnd.next=cur;
                    beforeEnd=beforeEnd.next;
                }
            }else {//cur.val>x,排在后面
                if (afterStart==null){
                    afterStart=cur;
                    afterEnd=cur;
                }else {
                    afterEnd.next=cur;
                    afterEnd=afterEnd.next;
                }
            }
            cur=cur.next;
        }
        if (beforeEnd==null){
            return afterStart;
        }
        beforeEnd.next=afterStart;//首位链接
        //第二段全为空，也是返回beforeStart足以
        /*if (afterStart==null){

        }*/
        //第二段不为空，最后一个节点的next值置Null
        if (afterEnd!=null){
            afterEnd.next=null;
        }
        return beforeStart;//返回小于x值的头节点
    }
    //判断是否有环
    //快慢指针
    public boolean hasCycle(Node head){
        Node fast=head;
        Node slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow;
            if (slow==fast){
                return true;
            }
        }
        return false;
    }
}
